package array

// https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
// // https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
// 两个数组的交集，输出不分顺序
// 算法: 通过 map 保存数据量较少的数组
// 时间复杂度: O(nlogn)
func intersect(nums1 []int, nums2 []int) []int {
	markMap := make(map[int]int)
	var biggerArr []int
	var shorterArr []int
	if len(nums1) > len(nums2) {
		biggerArr = nums1
		shorterArr = nums2
	} else {
		biggerArr = nums2
		shorterArr = nums1
	}

	retArr := make([]int, 0)
	for _, currentInt := range shorterArr {
		markMap[currentInt]++
	}
	for _, currentInt := range biggerArr {
		if markMap[currentInt] > 0 {
			markMap[currentInt]--
			retArr = append(retArr, currentInt)
		}
	}
	return retArr
}

// 进阶: 如果给定的数组已经排好序呢？你将如何优化你的算法？
//如果 nums1 的大小比 nums2 小很多，哪种方法更优？
//如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
